I.Contents:
˙Representations of graphs (adjacency matrix, adjacency list, sequential adjacency list etc).
˙Paths (including Eulerian tour, de Bruijn sequence, shortest path).
˙Trees (including minimum spanning tree, optimum branching, matroid, Huffman tree).
˙Depth first search (including applications to 2-connected component, strongly connected component, testing graph planarity etc)
˙Maximum flow (including Ford-Fulkerson’s algorithm, Diric’s algorithm, applications maximum flow theory such as connectivity and bipartite matching).
˙NP-completeness (including Cook’s theorem, SAT problem, transformations between NP-complete problems).
˙Others (some topics in current journals).
II.Course prerequisite:
None.
III. Reference material (textbook):
1.S. Even, Graph Algorithms, 1979. (textbook)
2.R. K. Ahuja, T. L. Magnanti andJ. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall International, London, 1993.
3.G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, New York, 1993.
4.W. J. Cook, W. H. Cunningham, W. R. Pulleyblank, A. Schrijver, Combinatorial Optimization, John Wiley & Sons, Inc., New York, 1998.
5.T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithm, Second Edition, The MIT Press, Cambridge, 2002.
6.A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
7.M. C. Golumbie, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
8.J. A. McHugh, Algorithmic Graph Theory, Prentice-Hall, London, 1990.
9.K. Thulasiraman and M. N. S. Swamy, Graphs: Theory and Algorithms, John Wiley & Sons, Inc., New York, 1992.
IV.Grading scheme:
50% for the midterm exam and 50% for the final exam.
V.Others:
Office: Room 305, Old Mathematics Building
Email: gjchang@math.ntu.edu.tw
http://www.math.ntu.edu.tw/~gjchang/